package leetcode.editor.cn;

import java.util.*;

public class P449SerializeAndDeserializeBst {
    public static void main(String[] args) {
        Codec ser = new P449SerializeAndDeserializeBst().new Codec();
//        TreeNode root = new TreeNode(2);
//        root.left = new TreeNode(1);
//        root.right = new TreeNode(3);
        String serialize = ser.serialize(null);
        System.out.println(serialize);

        Codec des = new P449SerializeAndDeserializeBst().new Codec();
        des.deserialize(serialize);
        System.out.println();

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            StringBuilder stringBuilder = new StringBuilder();
            while (!queue.isEmpty()) {
                int size = queue.size();
                while (size-- > 0) {
                    TreeNode poll = queue.poll();
                    stringBuilder.append("#");
                    if (poll == null) {
                        stringBuilder.append(null + "");
                        continue;
                    } else {
                        stringBuilder.append(poll.val + "");
                    }
                    if (poll.left != null) {
                        queue.offer(poll.left);
                    } else {
                        queue.offer(null);
                    }
                    if (poll.right != null) {
                        queue.offer(poll.right);
                    } else {
                        queue.offer(null);
                    }
                }
            }
            return stringBuilder.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            Queue<TreeNode> queue = new LinkedList<>();
            String[] split = data.split("#");
            if (split[1].equals("null")) {
                return null;
            }
            TreeNode root = new TreeNode((Integer.parseInt(split[1])));
            queue.offer(root);
            int index = 2;
            while (!queue.isEmpty() && index < split.length) {
                TreeNode poll = queue.poll();
                String left = split[index++];
                String right = split[index++];
                if (left != null && !left.equals("null")) {
                    poll.left = new TreeNode(Integer.parseInt(left));
                    queue.offer(poll.left);
                }
                if (right != null && !right.equals("null")) {
                    poll.right = new TreeNode(Integer.parseInt(right));
                    queue.offer(poll.right);
                }
            }
            return root;
        }
    }

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;
//leetcode submit region end(Prohibit modification and deletion)

}